package class8;

import common.TreeNode;
import common.TreeNodeUtils;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的序列化和反序列化
 * +      1
 * +    /  \
 * +   2    3
 * +  / \  / \
 * + 4  # 6   #
 * +# #  # #
 */
public class Code04_SerialAndReconstructTree {
    public static void main(String[] args) {
        TreeNode root = TreeNodeUtils.createTreeNode(1, 2, 3);
        TreeNode[] treeNodes = TreeNodeUtils.getTreeNodes(4, 5, 6, 7);
        TreeNode l = root.left;
        TreeNode r = root.right;
        l.left = treeNodes[0];
        r.left = treeNodes[2];
        Queue<String> res = preSerial(root);
        System.out.println("res = " + res);

        TreeNode treeNode = buildByPreQueue(res);
        System.out.println(treeNode);
    }

    /**
     * 先序方式的序列化
     * 1.利用 # 占位符，将空值存起来
     */
    public static Queue<String> preSerial(TreeNode head) {
        Queue<String> ans = new LinkedList<>();
        pres(head, ans);
        return ans;
    }

    private static void pres(TreeNode head, Queue<String> ans) {
        if (head == null) {
            ans.add("#");
        } else {
            ans.add(String.valueOf(head.val));
            pres(head.left, ans);
            pres(head.right, ans);
        }
    }

    /**
     * 二叉树反序列化
     */
    public static TreeNode buildByPreQueue(Queue<String> preList) {
        if (preList == null || preList.size() == 0) {
            return null;
        }
        return preb(preList);
    }

    public static TreeNode preb(Queue<String> preList) {
        String val = preList.poll();
        if (val.equals("#")) {
            return null;
        }
        TreeNode head = new TreeNode(Integer.valueOf(val));
        head.left = preb(preList);
        head.right = preb(preList);
        return head;
    }

}
